#include <iostream>
#include <string>

using std::cout;
using std::endl;
using std::string;

// a b c a b c a b d a
//-1 0 0 0 1 2 3 4 5 0 
void getNext(int *next, const string &t)
{
    int j = 0;
    int k = -1;
    next[j] = k;
    while(j < t.size() - 1){
        if(-1 == k || t[j] == t[k]){
            j++;
            k++;
            next[j] = k;
        }else{
            k = next[k];
        }

    }
    /* int j = 0;
    next[j] = -1;
    next[1] = 0;
    for(int i{2}; i < t.size(); i++){
        int k = next[i - 1];
        if(t[k] == t[i - 1]){
            next[i] = k + 1;
        }else{
            k = next[k];
            while(next[k] != -1 && t[k] != t[i - 1])
                k = next[k];
            next[i] = next[k] + 1;
        }
    } */

    for(int i{}; i < t.size(); i++){
        cout << next[i] << " ";
    }
    cout << endl;
}

bool contain(const string &s, const string &t)
{
    int next[t.size()] {0};
    getNext(next, t);

    int i = 0, j = 0;
    while(i < s.size() && j < (int)t.size()){
        if(-1 == j || s[i] == t[j]){
            i++;
            j++;
        }else{
            j = next[j];
        }
    }
    return j == t.size();
}

int main(int args, char *argv[])
{
    cout << contain("abcdabcabcabdagedae", "abcabcabda") << endl;
    return 0;
}